package _07_串;

public class _76_最小覆盖子串 {

    public static void main(String[] args) {
        _76_最小覆盖子串 v = new _76_最小覆盖子串();
        System.out.println((int)'A' - 'z');
        String str = "cgklivwehljxrdzpfdqsapogwvjtvbzahjnsejwnuhmomlfsrvmrnczjzjevkdvroiluthhpqtffhlzyglrvorgnalk";
        String t = "mqfff";
        System.out.println(v.minWindow(str, t));

    }

    public String minWindow(String s, String t) {
        int tLen = t.length();
        if (s.length() < tLen) return "";
        char[] chars = s.toCharArray();
        int[] list = new int[58];
        int sLen = chars.length;
        for (int i = 0; i < tLen; i++) {
            list[t.charAt(i) - 'A']++;
        }
        int left = 0;
        int right = left;
        int minLen = Integer.MAX_VALUE;
        int begin = 0;
        while (right < sLen) {
            // 右指针移动
            while (right < sLen && (--list[chars[right++] - 'A'] != 0 || !checkIsSuccess(list)));
            if (checkIsSuccess(list)) {
                // 左指针移动
                while (list[chars[left++] - 'A']++ != 0) ;
                int len = right - left + 1;
                if (len < minLen) {
                    minLen = len;
                    begin = left - 1;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : new String(chars, begin, minLen);
    }


    public boolean checkIsSuccess(int[] list) {
        // 没有大于0的元素
        for (int j : list) {
            if (j > 0) {
                return false;
            }
        }
        return true;
    }
}
